package com.unionfind_01;

/**
 * @Author: tgy
 * @Date: 1/12/21 5:31 PM
 *
 *    根据两个集合的大小来判断谁是根
 */
public class UF_QuickUnion_Size extends UF_QuickUnion {

    /**
     * 记录每个集合的元素个数
     */
    private int[] sizes;

    public UF_QuickUnion_Size(int size) {
        super(size);

        sizes = new int[size];

        for (int i = 0; i < size; i++) {

            sizes[i] = 1;
        }
    }

    @Override
    protected void justify(int p1, int p2) {

        if (sizes[p1] > sizes[p2]) {

            parents[p2] = p1;
            sizes[p1] += sizes[p2];
        }else {

            parents[p1] = p2;
            sizes[p2] += sizes[p1];
        }
    }

    public static void main(String[] args) {

        UF_QuickUnion quickUnion = new UF_QuickUnion_Size(9);


        quickUnion.union(1,3);
        quickUnion.union(2,8);
        quickUnion.union(4,7);
        quickUnion.union(3,4);

        System.out.println(quickUnion.isSame(1, 4));

    }

}
